#include<bits/stdc++.h>

using namespace std;

const int MX=33;

typedef pair<int,int> pii;
typedef unsigned int uint;
#define fr first
#define se second
#define pb push_back
#define mp make_pair

const int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
char a[MX][MX];char fch[MX*MX];
int bel[MX][MX];
vector<pii>f[MX*MX];int fc;
int n,m;

void dfs(int x,int y,char ch,int F){
	bel[x][y]=F;
	f[F].pb(mp(x,y));
	for(int d=0;d<4;d++){
		int xx=x+dx[d],yy=y+dy[d];
		if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&!bel[xx][yy]&&a[xx][yy]==ch)dfs(xx,yy,ch,F);
	}
}
char vis[MX];
char G[MX][MX],Gh[MX],Gn[MX][MX];
int up,dw,lf,rt;
uint C;
char _c[MX];
#define COL(i) ((i)<=fc?((C>>(i-1))&1):_c[i])
bool dfsr(int k,int t,int col){
	vis[k]=1;
	if(k==t)return true;
	for(int i=Gh[k];i;i=Gn[k][i])if(!vis[i]&&COL(i)==col&&dfsr(i,t,col))return true;
	return false;
}
bool bf(){
	up=fc+1,dw=fc+2,lf=fc+3,rt=fc+4;
	memset(G,0,sizeof(G));
	for(int i=1;i<=fc;i++)
		for(vector<pii>::iterator j=f[i].begin();j!=f[i].end();j++){
			int x=j->fr,y=j->se;
			for(int d=0;d<4;d++){
				int xx=x+dx[d],yy=y+dy[d];
				if(xx>n)G[i][dw]=1;
				else if(xx<1)G[i][up]=G[up][i]=1;
				else if(yy>m)G[i][rt]=G[rt][i]=1;
				else if(yy<1)G[i][lf]=G[lf][i]=1;
				else if(a[xx][yy]!=a[x][y])G[i][bel[xx][yy]]=G[bel[xx][yy]][i]=1;
			}
		}
	memset(Gh,0,sizeof(Gh)),memset(Gn,0,sizeof(Gn));
	int vc=fc+4;
	for(int i=1;i<=vc;i++){
		for(int j=1;j<=vc;j++)if(G[i][j])Gn[i][j]=Gh[i],Gh[i]=j;
	}
	_c[lf]=_c[rt]=0,_c[up]=_c[dw]=1;
	for(C=0;C<(1<<fc);C++){
		if(!(memset(vis,0,sizeof(vis)),dfsr(lf,rt,0))&&!(memset(vis,0,sizeof(vis)),dfsr(up,dw,1)))return false;
	}
	return true;
}
const int inf=0x3f3f3f3f;
#define QUA(x,y) (a[x][y]!=a[(x)+1][y]&&a[x][y]!=a[x][(y)+1]&&a[x][y]!=a[(x)+1][(y)+1]&&a[(x)+1][y]!=a[x][(y)+1]&&a[(x)+1][y]!=a[(x)+1][(y)+1]&&a[x][(y)+1]!=a[(x)+1][(y)+1]) 
namespace Flow{
	struct Edge{
		int t,r,nxt;
		Edge(int _t=0,int _r=0,int _nxt=0):t(_t),r(_r),nxt(_nxt){}
	}e[MX*MX*2*31];
	int S,T,vc;
	int ec,hed[MX*MX*2],cur[MX*MX*2];
	inline void ade(int f,int t,int c){
		//printf("%d %d %d\n",f,t,c);
		e[++ec]=Edge(t,c,hed[f]),hed[f]=ec;
		e[++ec]=Edge(f,0,hed[t]),hed[t]=ec;
	}
	int d[MX*MX*2];
	bool bfs(){
		static int q[MX*MX*2];
		int h=0,t=0;
		memset(d+1,-1,sizeof(int)*vc);
		d[S]=0;q[++t]=S;
		while(h<t){
			int r=q[++h];
			for(int i=hed[r];i;i=e[i].nxt)if(e[i].r&&d[e[i].t]==-1){
				d[e[i].t]=d[r]+1,q[++t]=e[i].t;
			}
		}
		return d[T]!=-1;
	}
	int dfs(int k,int mx){
		if(k==T||!mx)return mx;
		int ans=0;
		for(int &i=cur[k];i;i=e[i].nxt)if(e[i].r&&d[e[i].t]==d[k]+1){
			int f=dfs(e[i].t,min(mx,e[i].r));
			//if(f)
				//printf("%d %c\n",k,(k<=(fc+4)*2&&(k-1)%(fc+4)+1<=fc?fch[(k-1)%(fc+4)+1]:'#'));
			ans+=f,mx-=f;
			e[i].r-=f,e[i^1].r+=f;
			if(!mx)break;
		}
		return ans;
	}
	int dinic(){
		int ans=0;
		while(bfs()){
			memcpy(cur+1,hed+1,sizeof(int)*vc);
			ans+=dfs(S,inf);
			//puts("");
		}
		return ans;
	}
	void ini(){
		vc=(fc+4)*2+2;S=vc-1,T=vc;
		ec=1;memset(hed+1,0,sizeof(int)*vc);
	}
};
using Flow::ade;
using Flow::dinic;
using Flow::S;
using Flow::T;
bool ck_wk(int x,int y){
	//(x,y) (x+1,y) (x+1,y+1) (x,y+1) 是否恰好能各与某条边一一对应相连。网络流判断 
	//if(x==10&&y==28){
	//	puts("!!!");
	//}
	Flow::ini();
	int CC=fc+4;
	for(int i=1;i<=fc;i++)
		for(vector<pii>::iterator j=f[i].begin();j!=f[i].end();j++){
			int x=j->fr,y=j->se;
			for(int d=0;d<4;d++){
				int xx=x+dx[d],yy=y+dy[d];
				if(xx>n)ade(CC+i,dw,inf),ade(CC+dw,i,inf);
				else if(xx<1)ade(CC+i,up,inf),ade(CC+up,i,inf);
				else if(yy>m)ade(CC+i,rt,inf),ade(CC+rt,i,inf);
				else if(yy<1)ade(CC+i,lf,inf),ade(CC+lf,i,inf);
				else if(a[xx][yy]!=a[x][y])
					ade(CC+i,bel[xx][yy],inf),ade(CC+bel[xx][yy],i,inf);
			}
		}
	for(int i=1;i<=CC;i++)ade(i,CC+i,1);
	ade(S,bel[x][y],1),ade(S,bel[x+1][y],1),ade(S,bel[x][y+1],1),ade(S,bel[x+1][y+1],1);
	ade(CC+lf,T,1),ade(CC+up,T,1),ade(CC+rt,T,1),ade(CC+dw,T,1);
	return dinic()==4;
}
bool wk(){
	up=fc+1,dw=fc+2,lf=fc+3,rt=fc+4;
	for(int i=1;i<n;i++)
		for(int j=1;j<m;j++)
			if(QUA(i,j)&&ck_wk(i,j)){
				//fprintf(stderr,"%d %d\n",i,j);
				return false;
			}
	return true;
}
int main(){
	freopen("T2.in","r",stdin);
	freopen("T2.out","w",stdout);
	int T;scanf("%d",&T);
	while(T--){
		scanf("%d",&n);
		memset(a,0,sizeof(a));
		for(int i=1;i<=n;i++)scanf("%s",a[i]+1);
		m=strlen(a[1]+1);
		memset(bel,0,sizeof(bel));
		fc=0;
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++)
				if(!bel[i][j]){
					f[++fc].clear();
					fch[fc]=a[i][j];
					dfs(i,j,a[i][j],fc);
				}
		if(fc<=18)puts(bf()?"valid":"invalid");
		else puts(wk()?"valid":"invalid");
	}
	return 0;
}
